package string;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class MinimumWindowSubstring76 {
    public String minWindow(String s, String t) {
        if (t == null || t.equals("")) {
            return "";
        }

        Map<Character, Integer> tt = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            tt.put(c, tt.getOrDefault(c, 0) + 1);
        }

        boolean isValid = false;

        int begin = 0;
        int end = 0;

        Map<Character, Integer> ss = new HashMap<>();
        String result = "";
        while (end <= s.length()) {
            if (isValid) {
                if (tt.containsKey(s.charAt(begin)) && ss.containsKey(s.charAt(begin))) {
                    ss.put(s.charAt(begin), ss.get(s.charAt(begin)) - 1);
                }
                begin++;

            } else {
                if(end == s.length()){
                    break;
                }
                if (tt.containsKey(s.charAt(end))) {
                    ss.put(s.charAt(end), ss.getOrDefault(s.charAt(end), 0) + 1);
                }
                end++;
            }
            isValid = checkValid(ss, tt);
            if (isValid && (result.length() == 0 || end - begin < result.length())) {
                result = s.substring(begin, end);
            }

        }
        return result;
    }

    private boolean checkValid(Map<Character, Integer> ss, Map<Character, Integer> tt) {
        for (Map.Entry<Character, Integer> entry : tt.entrySet()
        ) {
            if (!ss.containsKey(entry.getKey())) {
                return false;
            } else {
                if (ss.get(entry.getKey()) < entry.getValue()) {
                    return false;
                }
            }
        }
        return true;
    }

}
